class Solution {
public:
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
     
    // 不超出Integer的斐波那契数很少，仅有50个左右。不考虑溢出。

// - 递归定义，自顶向下，复杂度O(N!)，只是教学用的反例
// - 开数组，从下到上，初学者能独立发明
// - 三个变量，交替遍历，编程小技巧
// - 代数方法，O(LogN)，(fn fn-1) = (fn-1 fn-2)*A
// - 求通项公式，O(1)，见《编程之美》
// http://setosa.io/ev/eigenvectors-and-eigenvalues/
// http://www.vartang.com/2013/06/fibonacci/

    int fibonacci(int n) {
        // 使用纯的递归，复杂度是O(2^n)
        // if (n <= 2) return n - 1;
        // return fibonacci(n - 2) + fibonacci(n - 1);
    
        // 用数组存储计算过的项, 时间O(N), 空间O(N)
        // vector<int> nums(n, 0);
        // nums[0] = 0;
        // nums[1] = 1;
        // for (int i = 2; i < n; ++i)
        // {
        //     nums[i] = nums[i - 1] + nums[i - 2];
        // }
        // return nums[n - 1];
    
        // int a = 0;
        // int b = 1;
        // for (int i = 0; i < n - 1; ++i)
        // {
        //     int tmp = a + b;
        //     a = b;
        //     b = tmp;
        // }
        // return a;
        
        
        if(n == 1){
            return 0;
        }
        if(n == 2 || n == 3){
            return 1;
        }
        int ave = n / 2;
        if(n % 2 == 0){
            return fibonacci(ave)*fibonacci(ave)
                + fibonacci(ave + 1)*fibonacci(ave + 1);
        }
        return fibonacci(ave)*fibonacci(ave + 1)
            + fibonacci(ave + 2)*fibonacci(ave + 1);
    }
};